#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义一个结点，表示赫夫曼树的一个节点
typedef struct {
    int weight;  // 结点的权重（频率）
    int parent, left, right;  // 父结点、左孩子结点、右孩子结点
} HNode;

// 定义赫夫曼编码表
typedef struct {
    char character;  // 字符
    char code[100];  // 赫夫曼编码
} HuffmanCode;

// 选择两个最小的结点
void selectMin(HNode* tree, int n, int* s1, int* s2) {
    int min1 = 1000000, min2 = 1000000;  // 初始化最小权重为最大值
    *s1 = *s2 = -1;
    
    for (int i = 0; i < n; i++) {
        // 找到两个最小的结点
        if (tree[i].parent == -1) {
            if (tree[i].weight < min1) {
                min2 = min1;
                *s2 = *s1;
                min1 = tree[i].weight;
                *s1 = i;
            } else if (tree[i].weight < min2 && i != *s1) {
                min2 = tree[i].weight;
                *s2 = i;
            }
        }
    }
}

// 生成赫夫曼树
void createHuffmanTree(HNode* tree, int* weights, int n) {
    int m = 2 * n - 1;  // 总结点数，2n-1个结点
    
    // 初始化赫夫曼树
    for (int i = 0; i < n; i++) {
        tree[i].weight = weights[i];
        tree[i].parent = tree[i].left = tree[i].right = -1;  // 初始化为 -1，表示没有父结点和孩子
    }
    for (int i = n; i < m; i++) {
        tree[i].weight = 0;
        tree[i].parent = tree[i].left = tree[i].right = -1;
    }

    // 逐步合并节点
    for (int i = n; i < m; i++) {
        int s1, s2;
        selectMin(tree, i, &s1, &s2);  // 选择两个最小的结点
        
        if (s1 == -1 || s2 == -1) {
            printf("错误：无法找到两个最小节点\n");
            return;
        }
        
        tree[s1].parent = tree[s2].parent = i;  // 设置父结点
        tree[i].left = s1;
        tree[i].right = s2;
        tree[i].weight = tree[s1].weight + tree[s2].weight;  // 新结点的权重是两个子结点权重之和
    }
}

// 生成赫夫曼编码
void generateHuffmanCode(HNode* tree, HuffmanCode* huffmanCodes, int n) {
    for (int i = 0; i < n; i++) {
        char tempCode[100] = "";  // 临时存储编码
        int current = i;
        int parent = tree[current].parent;
        int index = 0;
        
        // 从叶子节点回溯到根节点
        while (parent != -1) {
            if (tree[parent].left == current) {
                tempCode[index++] = '0';
            } else {
                tempCode[index++] = '1';
            }
            current = parent;
            parent = tree[current].parent;
        }
        
        tempCode[index] = '\0';  // 添加字符串结束符
        
        // 反转编码（因为是从叶子到根生成的）
        int len = strlen(tempCode);
        for (int j = 0; j < len; j++) {
            huffmanCodes[i].code[j] = tempCode[len - 1 - j];
        }
        huffmanCodes[i].code[len] = '\0';
    }
}

// 打印赫夫曼编码
void printHuffmanCodes(HuffmanCode* huffmanCodes, int n) {
    printf("打印赫夫曼编码：\n");
    for (int i = 0; i < n; i++) {
        printf("%c : %s\n", huffmanCodes[i].character, huffmanCodes[i].code);
    }
}

// 打印赫夫曼树结构（调试用）
void printHuffmanTree(HNode* tree, int n) {
    printf("\n赫夫曼树结构：\n");
    printf("索引\t权重\t父节点\t左孩子\t右孩子\n");
    for (int i = 0; i < 2 * n - 1; i++) {
        printf("%d\t%d\t%d\t%d\t%d\n", 
               i, tree[i].weight, tree[i].parent, tree[i].left, tree[i].right);
    }
}

int main() {
    int n;
    printf("输入字符个数：");
    scanf("%d", &n);

    if (n <= 0) {
        printf("错误：字符个数必须大于0\n");
        return 1;
    }

    char characters[n];
    int frequencies[n];
    printf("输入字符及其频率：\n");
    for (int i = 0; i < n; i++) {
        getchar();  // 读取换行符
        printf("字符%d：", i + 1);
        scanf("%c", &characters[i]);
        printf("频率：");
        scanf("%d", &frequencies[i]);
        
        if (frequencies[i] < 0) {
            printf("错误：频率不能为负数\n");
            return 1;
        }
    }

    // 生成赫夫曼树
    HNode tree[2 * n - 1];
    createHuffmanTree(tree, frequencies, n);

    // 生成赫夫曼编码
    HuffmanCode huffmanCodes[n];
    for (int i = 0; i < n; i++) {
        huffmanCodes[i].character = characters[i];
    }
    generateHuffmanCode(tree, huffmanCodes, n);

    // 打印赫夫曼编码
    printHuffmanCodes(huffmanCodes, n);

    return 0;
}